
'''
  This class represent an set of tests for AVL Tree, an AVL tree is a self-balancing
  binary search tree, and it was the first such data structure to 
  be invented. In an AVL tree, the heights of the two child subtrees 
  of any node differ by at most one; if at any time they differ 
  by more than one, rebalancing is done to restore this property.

  Author: Samuel T. C. Santos
  Date  : 2013/04/19

'''

from avl import AVL

class AVLTest:

	def __init__(self):
		print("init AVL Tree tests: ")

	''' 
	    scenario test

	  	insert(5)            balanced tree
	  	insert(10)                   10
	  	insert(15)                 /    \
	  	insert(20)                5     15
	  	                                  \
	  	                                  20
	  	remove(5)             unbalanced tree
	  	                            10
	  	                              \
	  	                               15
	  	                                \
	  	                                20
	  	rebalanceUp()         balanced tree
	  	                             15
	  	                            /  \
	  	                          10    20
	'''
	def runTestRebalanceUp(self):
		avl = AVL()
		
		avl.insert(5)
		
		root = avl.getRoot()

		assert(root.getData() == 5)
		assert(root.getParent().isEmpty() == True)

		root = avl.getRoot()
		avl.insert(10)

		assert(root.getParent().isEmpty() == True)

		avl.insert(15)
		root = avl.getRoot()

		assert(root.getParent().isEmpty() == True)

		root = avl.getRoot()
		avl.insert(20)

		assert(avl.preOrder() == [10, 5, 15, 20])
		
		avl.remove(5)

		root = avl.getRoot()
		assert(root.getData() == 15)

		assert(root.getParent().isEmpty() == True)
		
		assert(root.getLeft().getData() == 10)
		assert(root.getRight().getData() == 20)		

		avl.remove(10)
		avl.remove(15)
		avl.remove(20)


		assert(avl.size() == 0)
		
		print("Done, test runTestRebalanceUp OK!")


	'''
        Balance AVL Example:

    	insert(5)            5           height=0  -- balanced
    	insert(10)            \ 
    	insert (15)           10         height=1  -- balanced
    	                        \ 
    	                        15       height=2  -- unbalanced

    	rebalance()              10      height=0  -- balanced
    	                        /  \
    	                       5    15   height=1  -- balanced
        insert(3)             /
                             3           height=2  -- balanced
        insert(4)             \
                               4         height=3  -- unbalanced
        rebalance()          

                                  10                10
                                /   \               / \
                               5     15            4  15 
                              /           next    / \ 
                             4            ---    3   5
                            /
                           3     
    '''
	def runTestBalance(self):
		avl = AVL()

		avl.insert(5)
		assert(avl.height() == 0)


		avl.insert(10)
		assert(avl.height() == 1)

		avl.insert(15)
		assert(avl.height() == 1) 
		#height should be 1, because the tree was rebalanced!

		avl.insert(3)
		assert(avl.height() == 2)

		avl.insert(4)

		root = avl.getRoot()
		
		#assert(root.getData()==5)
		print(root.getLeft().getData())
		print("Done, test runTestBalance OK!")


	def runTestBalanceFactor(self):
		avl = AVL()

		avl.insert(9)
		assert(avl.balanceFactor(9) == 0)

		avl.insert(5)
		assert(avl.balanceFactor(9) == 1)

		avl.insert(3)
		assert(avl.balanceFactor(9) == 2)

		print("Done, test RunBalanceFactor OK!")


	'''
	 Right Rotation example:

	                   17
                      /    right rotation      11
                    11        ----->         /    \
                   /                        7     17
                  7
	'''
	def runTestRightRotation(self):
		avl = AVL()

		avl.insert(17)
		avl.insert(11)
		avl.insert(7)

		assert(avl.balanceFactor(17) == 2)

		avl.rightRotation(17)

		assert(avl.balanceFactor(11) == 0)

		root = avl.getRoot()

		assert(root.getLeft().getData() == 7)
		assert(root.getData() == 11)
		assert(root.getRight().getData() == 17)

		print("Done, test RunTestRightRotation OK!")


	'''
				7
				  \      left rotation    11 
				   11       ---->       /     \
				     \                 7       17
				      17
	'''
	def runTestLeftRotation(self):
		avl = AVL()

		avl.insert(7)
		avl.insert(11)
		avl.insert(17)

		assert(avl.balanceFactor(7) == -2)

		avl.leftRotation(7)

		assert(avl.balanceFactor(11) == 0)

		root = avl.getRoot()
		
		assert(root.getLeft().getData() == 7)
		assert(root.getData() == 11)
		assert(root.getRight().getData() == 17)

		print("Done, test RunTestLeftRotation OK!")
 		



if __name__ == '__main__':
	test = AVLTest()
	#test.runTestBalanceFactor()
	#test.runTestLeftRotation()
	#test.runTestRightRotation()
	#test.runTestBalance()
	test.runTestRebalanceUp()

